#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct KeyValuePair {
    int key;
    void *value;
    struct KeyValuePair *next; // 处理哈希冲突，使用链表
} KeyValuePair;

typedef struct HashMap {
    KeyValuePair **buckets; // 桶数组
    size_t table_size;      // 哈希表大小
} HashMap;

// 哈希函数
size_t hash(int key, size_t table_size) {
    return key % table_size;
}

// 创建哈希表
HashMap* create_map(size_t table_size) {
    HashMap *map = (HashMap*)malloc(sizeof(HashMap));
    if (!map) return NULL;

    map->table_size = table_size;
    map->buckets = (KeyValuePair**)calloc(table_size, sizeof(KeyValuePair*));
    if (!map->buckets) {
        free(map);
        return NULL;
    }

    return map;
}

// 插入键值对
void insert(HashMap *map, int key, void *value) {
    size_t index = hash(key, map->table_size);

    // 创建新的键值对
    KeyValuePair *new_pair = (KeyValuePair*)malloc(sizeof(KeyValuePair));
    new_pair->key = key;
    new_pair->value = value;
    new_pair->next = NULL;

    // 插入到链表的头部
    KeyValuePair *bucket = map->buckets[index];
    if (bucket == NULL) {
        map->buckets[index] = new_pair;
    } else {
        new_pair->next = bucket;
        map->buckets[index] = new_pair;
    }
}

// 查找键对应的值
void* get(HashMap *map, int key) {
    size_t index = hash(key, map->table_size);
    KeyValuePair *bucket = map->buckets[index];

    // 遍历链表查找
    while (bucket != NULL) {
        if (bucket->key == key) {
            return bucket->value;
        }
        bucket = bucket->next;
    }

    return NULL; // 如果找不到
}

// 删除键值对
void del(HashMap *map, int key) {
    size_t index = hash(key, map->table_size);
    KeyValuePair *bucket = map->buckets[index];
    KeyValuePair *prev = NULL;

    // 遍历链表查找并删除
    while (bucket != NULL) {
        if (bucket->key == key) {
            if (prev == NULL) {
                map->buckets[index] = bucket->next; // 删除头节点
            } else {
                prev->next = bucket->next; // 删除中间或尾部节点
            }
            free(bucket);
            return;
        }
        prev = bucket;
        bucket = bucket->next;
    }
}

// 释放哈希表的内存
void free_map(HashMap *map) {
    for (size_t i = 0; i < map->table_size; ++i) {
        KeyValuePair *bucket = map->buckets[i];
        while (bucket != NULL) {
            KeyValuePair *temp = bucket;
            bucket = bucket->next;
            free(temp);
        }
    }
    free(map->buckets);
    free(map);
}

// 测试
int main() {
    // 创建哈希表
    HashMap *map = create_map(10);

    // 插入键值对
    int value1 = 100;
    int value2 = 200;
    insert(map, 1, &value1);
    insert(map, 2, &value2);

    // 查找键值
    int *found_value = (int*)get(map, 1);
    if (found_value) {
        printf("Found key 1 with value: %d\n", *found_value);
    } else {
        printf("Key 1 not found\n");
    }

    // 删除键值对
    del(map, 1);
    found_value = (int*)get(map, 1);
    if (found_value) {
        printf("Found key 1 with value: %d\n", *found_value);
    } else {
        printf("Key 1 not found\n");
    }

    // 释放哈希表
    free_map(map);

    return 0;
}
